package com.sj.thread.c_026;

import java.util.Arrays;
import java.util.Random;

public class Demo {
    int[] a;
    char[] op;
    Random random = new Random(0);

    void generateProblem() {
        int n = random.nextInt(60) + 1;
        a = new int[n];
        op = new char[n];
        for (int i = 0; i < n; i++) {
            a[i] = random.nextInt(200);
            if (i == 0) op[i] = '+';
            else {
                op[i] = random.nextBoolean() ? '+' : '-';
            }
        }
    }

    //暴力方法求正确答案
    class Bruteforce {
        int min[][] = new int[a.length][a.length];
        int max[][] = new int[a.length][a.length];

        int solve() {
            for (int i = 0; i < a.length; i++) {
                min[i][i] = a[i];
                max[i][i] = a[i];
            }
            for (int step = 1; step < a.length; step++) {
                for (int i = 0; i + step < a.length; i++) {
                    int f = i, t = i + step;
                    int s = a[f];
                    for (int j = f + 1; j <= t; j++) {
                        s += (op[j] == '+' ? 1 : -1) * a[j];
                    }
                    min[f][t] = max[f][t] = s;
                    for (int j = f + 1; j <= t; j++) {
                        if (op[j] == '-') {
                            int nowMax = max[f][j - 1] - min[j][t];
                            int nowMin = min[f][j - 1] - max[j][t];
                            min[f][t] = Math.min(min[f][t], nowMin);
                            max[f][t] = Math.max(max[f][t], nowMax);
                        }
                    }
                }
            }
            return max[0][a.length - 1];
        }
    }

    //最好的方法
    class Best {
        int[] a;
        char[] op;

        int max[];//max[i]表示从i到末尾表达式的最大值
        int suffix[];//min[i]表示从i到末尾表达式的最小值

        //压缩正号
        void compress() {
            int i = 0;
            a = Arrays.copyOf(Demo.this.a, Demo.this.a.length);
            op = Arrays.copyOf(Demo.this.op, Demo.this.op.length);
            for (int j = 1; j < a.length; j++) {
                if (op[i] == '+' && op[j] == '+') {
                    a[i] += a[j];
                } else {
                    i++;
                    op[i] = op[j];
                    a[i] = a[j];
                }
            }
            a = Arrays.copyOf(a, i + 1);
            op = Arrays.copyOf(op, i + 1);
        }


        int solve() {
            compress();
            max = new int[a.length];
            suffix = new int[a.length];
            suffix[suffix.length - 1] = a[suffix.length - 1];
            for (int i = suffix.length - 2; i >= 0; i--) {
                suffix[i] = a[i] + suffix[i + 1];
            }
            max[a.length - 1] = a[a.length - 1];
            for (int i = a.length - 2; i >= 0; i--) {
                if (op[i + 1] == '+') {
                    max[i] = max[i + 1] + a[i];
                } else {
                    if (i + 2 >= a.length) {
                        max[i] = a[i] - a[i + 1];
                        continue;
                    }
                    if (op[i + 2] == '-') {//连续两个减号
                        max[i] = a[i] - a[i + 1] + suffix[i + 2];
                    } else {//-+-
                        //一括到底
                        int s = a[i] - a[i + 1] - a[i + 2] + (i + 3 < suffix.length ? suffix[i + 3] : 0);
                        //只扩一个
                        int ss = a[i] - a[i + 1] + max[i + 2];
                        max[i] = Math.max(s, ss);
                    }
                }
            }
            return max[0];
        }
    }

    String tos() {
        StringBuilder builder = new StringBuilder();
        builder.append(a[0]);
        for (int j = 1; j < a.length; j++) {
            builder.append(op[j]).append(a[j]);
        }
        return builder.toString();
    }

    Demo() {
            generateProblem();
            System.out.println(tos());
            int ans = new Bruteforce().solve();
            int mine = new Best().solve();
            System.out.println("ans:" + ans + " mine:" + mine);
            if (ans != mine) {
                throw new RuntimeException("error");
            }
    }

    public static void main(String[] args) {
        new Demo();
    }
}
